package leetcode;

/**
 * <p></p>
 *
 * @author bin.zhang
 * <p/>
 * Revision History:
 * 2020/09/10, 初始化版本
 * @version 1.0
 **/
public class FindMedianSortedArrays {


	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		int nums1Length = nums1.length, nums2Length = nums2.length;
		int media = (nums1Length + nums2Length)/2 ;
		int i = 0, j = 0;
		int media1 = 0;
		int media2 = 0;
		if((nums1Length + nums2Length) % 2 == 0){
			while (i+j <= media + 1){
				if(i + j == media){
					media1 = i == 0 ? nums2[j-1] : j == 0 ? nums1[i-1] :Math.max(nums1[i-1], nums2[j-1]);
				}
				if(i + j == media + 1){
					media2 = i == 0 ? nums2[j-1] : j == 0 ? nums1[i-1] :Math.max(nums1[i-1], nums2[j-1]);
				}
				if(j != nums2Length && (i == nums1Length || nums1[i] >= nums2[j])){
					j++;
				}else{
					i++;
				}
			}
			return (media1 + media2)/2.0;
		}
		while (i+j <= media + 1){
			if(i + j == media + 1){
				media1 = i == 0 ? nums2[j-1] : j == 0 ? nums1[i-1] :Math.max(nums1[i-1], nums2[j-1]);
			}
			if(i == nums1Length - 1 || nums1[i] >= nums2[j]){
				j++;
			}else{
				i++;
			}
		}
		return media1;
	}





	private int findLessThenCount(int num, int[] nums){
		int cursor = nums.length/2;
		int cursorStart = 0;
		int cursorEnd = nums.length - 1;
		int segLength;
		while (num > nums[cursor + 1] || num < nums[cursor]){
			if(num <=  nums[cursor]){
				cursorEnd = cursor;
				segLength = cursorEnd - cursorStart;
				cursor = cursor - (segLength + 1) / 2;
				if(cursor <= cursorStart){
					break;
				}
				continue;
			}
			if(num >= nums[cursor]){
				cursorStart = cursor;
				segLength = cursorEnd - cursorStart;
				cursor = cursor + (segLength + 1)/2;
				if(cursor >= cursorEnd){
					break;
				}
			}
		}
		return cursor + 1;
	}




	public static void main(String[] args){
		int[] num1 = new int[]{0,0};
		int[] num2 = new int[]{0,0};
		System.out.println(new FindMedianSortedArrays().findMedianSortedArrays(num1, num2));
	}

}
